Search results for "Binary Relation"
showing 10 items of 11 documents
Elementary Action Systems
2015
This chapter expounds basic notions. An elementary action system is a triple consisting of the set of states, the transition relation between states, and a family of binary relations defined on the set of states. The elements of this family are called atomic actions. Each pair of states belonging to an atomic action is a possible performance of this action. This purely extensional understanding of atomic actions is close to dynamic logic. Compound actions are defined as sets of finite sequences of atomic actions. Thus compound actions are regarded as languages over the alphabet whose elements are atomic actions. This chapter is concerned with the problem of performability of actions and the…
On the use of relational expressions in the design of efficient algorithms
2005
Relational expressions have finite binary relations as arguments and the operations are composition (·), closure (*), inverse (−1), and union (U). The efficient computation of the relation denoted by a relational expression is considered, and a tight bound is established on the complexity of the algorithm suggested by Hunt, Szymanski and Ullman. The result implies a unified method for deriving efficient algorithms for many problems in parsing. For example, optimal algorithms are derived for strong LL(1) and strong LL(2) parser construction and an efficient polynomialtime algorithm is derived for determining the inessential error entries in an LR(1) parsing table.
Ordering and Convex Polyominoes
2005
We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q≼P are polyominoes. In the seco…
Knowledge Representation in Extended Pawlak’s Information Systems: Algebraic Aspects
2002
The notion of an information system in Pawlak's sense is extended by introducing a certain ordering on the attribute set, which allows to treat some attributes as parts of others. With every extended information system S associated is the set K(S) of those pieces of information that, in a sense, admit a direct access in S. The algebraic structure of the "information space" K(S) is investigated, and it is shown, in what extent the structure of S can be restored from the structure of its information space. In particular, an intrinsic binary relation on K(S), interpreted as entailment, is isolated, and an axiomatic description of a knowledge revision operation based on it is proposed.
Performability of Actions
2021
AbstractAction theory may be regarded as a theoretical foundation of AI, because it provides in a logically coherent way the principles of performing actions by agents. But, more importantly, action theory offers a formal ontology mainly based on set-theoretic constructs. This ontology isolates various types of actions as structured entities: atomic, sequential, compound, ordered, situational actions etc., and it is a solid and non-removable foundation of any rational activity. The paper is mainly concerned with a bunch of issues centered around the notion of performability of actions. It seems that the problem of performability of actions, though of basic importance for purely practical ap…
SEA presidential address: Group connectivity and cooperation
2011
A model-free methodology is used for the first time to estimate a daily volatility index (VIBEX-NEW) for the Spanish financial market.We use a public data set of daily option prices to compute this index and showthat daily changes in VIBEXNEW display a negative, tight contemporaneous relationship with IBEX daily returns, contrary to other common volatility indicators, as an implied volatility indicator or a GARCH(1,1) conditional volatility model. This relationship is approximately symmetric to the sign on VIBEX-NEW changes and asymmetric to the IBEX-35 returns sign, which make it clearly a suitable volatility index for the Spanish stock market. We also examine the relationship between curr…
An Algebraic Approach to Knowledge Representation
1999
This paper is an attempt to apply domain-theoretic ideas to a new area, viz. knowledge representation. We present an algebraic model of a belief system. The model consists of an information domain of special kind (belief algebra) and a binary relation on it (entailment). It is shown by examples that several natural belief algebras are, essentially, algebras of flat records. With an eye on this, we characterise those domains and belief algebras that are isomorphic to domains or algebras of records. For illustration, we suggest a system of axioms for revision in such a model and describe an explicit construction of what could be called a maxichoise revision.
Efficient evaluation for a subset of recursive queries
1991
Abstract We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluat…
Unit Operations in Approximation Spaces
2010
Unit operations are some special functions on sets. The concept of the unit operation originates from researches of U. Wybraniec-Skardowska. The paper is concerned with the general properties of such functions. The isomorphism between binary relations and unit operations is proved. Algebraic structures of families of unit operations corresponding to certain classes of binary relations are considered. Unit operations are useful in Pawlak's Rough Set Theory. It is shown that unit operations are upper approximations in approximation space. We prove, that in the approximation space (U, R) generated by a reflexive relation R the corresponding unit operation is the least definable approximation i…
Connections Between Single-Level and Bilevel Multiobjective Optimization
2011
The relationship between bilevel optimization and multiobjective optimization has been studied by several authors and there have been repeated attempts to establish a link between the two. We unify the results from the literature and generalize them for bilevel multiobjective optimization. We formulate sufficient conditions for an arbitrary binary relation to guarantee equality between the efficient set produced by the relation and the set of optimal solutions to a bilevel problem. In addition, we present specially structured bilevel multiobjective optimization problems motivated by real-life applications and an accompanying binary relation permitting their reduction to single-level multiob…